package cn.jdemo.algorithm.dynamicProgramming;

/**
 * @subject
 * 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
 * 返回 你可以获得的最大乘积 。
 *
 * @thinking
 * 动规五部曲
 * 1.确定dp数组（dp table）以及下标的含义
 * --- dp[i],分拆数字i后-可以得到的最大乘积
 * 2.确定递推公式
 * --- dp[i] = max( dp[i], max((i-j)*j,dp[i-j]*j) );
 * 3.dp的初始化
 * dp[2] = 1,dp[1]与dp[0]无解
 * 4.确定遍历顺序
 * 5.举例推导dp数组
 */
public class IntegerPartition {
    public static void main(String[] args) {
        int res = new IntegerPartition().integerBreak(10);
        System.out.println(res);
    }
    public int integerBreak(int n) {
        int[] dp = new int[n+1];// 下标最大为n
        if (n == 2){
            dp[n] = 1;
        }
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max( dp[i], Math.max(j*(i-j),j*dp[i-j]) );
            }
        }
        return dp[n];
    }
}
